package 七大排序;

import java.util.concurrent.ThreadLocalRandom;

public class SevenSort {
    ThreadLocalRandom localRandom = ThreadLocalRandom.current();
    public static void main(String[] args) throws ClassNotFoundException {
        int n = 10000000;
        int[] arr = SortTest.createRandomArr(n);
        int[] arr1 = SortTest.copyArr(arr);
        int[] arr2 = SortTest.copyArr(arr);
        int[] arr3 = SortTest.copyArr(arr);
//        SortTest.randomArrTest(arr1,"selectionSort");
//        SortTest.randomArrTest(arr3,"binaryInsertSort");
//        SortTest.randomArrTest(arr2,"insertSort");
        SortTest.randomArrTest(arr,"heapSort");
        SortTest.randomArrTest(arr1,"quickSort");
        SortTest.randomArrTest(arr3,"quickSort1");
    }

    public void binaryInsertSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {

            int val = arr[i];
            int left = 0;
            int right = i;
            while (left < right){
                int mid = (left + right)/2;
                if (val < arr[mid]){
                    right = mid;

                }else {
                    left = mid+1;
                }
            }
            for (int j = i;j > left;j--){
                arr[j] = arr[j-1];
            }
            arr[left] = val;
        }
    }

    public void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //如果当前元素小于前面的元素，就一直向前移动
            for (int j = i; j > 0 ; j--) {
                if (arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }else {
                    break;
                }
            }
        }
    }

    public void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            if (!flag){
                return;
            }
        }
    }

    public void selectionSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[min])
                    min = j;
            }
            swap(arr,min,i);
        }
    }

    public void selectionSortOB(int[] arr){
        int low = 0;
        int high = arr.length - 1;

        while (low < high){
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] > arr[max]){
                    max = i;
                }
                if (arr[i] < arr[min]){
                    min = i;
                }
            }
            swap(arr,min,low);
            if (max == low) {
                max = min;
            }
            swap(arr, max, high);
            low++;
            high--;
        }
    }

    /**
     * 尚硅谷快排
     * @param arr
     * @param left
     * @param right
     */
    public void quickSort(int[] arr,int left,int right){
        int l = left;
        int r = right;
        int mid = l + (r - l)/2;
        int point = arr[mid];
        while (l < r){
            while (arr[l] < point){
                l ++;
            }
            while (arr[r] > point){
                r--;
            }

            if (l >= r){
                break;
            }
            //l > point,r < point
            swap(arr,l,r);

            if (arr[l] == point){
                r--;
            }
            if (arr[r] == point){
                l++;
            }
        }
        if (l == r){
            l ++ ;
            r --;
        }
        if (left < r){
            quickSort(arr,left,r);
        }
        if (l < right){
            quickSort(arr,l,right);
        }
    }

    public void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
    }

    /**
     * 比特快排
     * @param arr
     */
    public void quickSort1(int[] arr){
        quickSort1(arr,0,arr.length - 1);
    }

    public void quickSort1(int[] arr ,int left,int right){
        if (left >= right){
            return;
        }
        //先让全部的元素划分为左边全部小于v，右边全部大于v。
        int p = partition(arr,left,right);
        //在将左右两边的元素全部有序。
        quickSort1(arr,left,p-1);
        quickSort1(arr,p+1,right);
    }

    /**
     * 快速排序的核心排序方法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] arr, int left, int right) {
        int anInt = localRandom.nextInt(left, right);
        swap(arr,left,anInt);
        int v = arr[left];
        //前闭后闭，[left + 1, j]为所有小于v的元素的区间
        int j = left;//[left + 1,left]为空区间，初始位置为0

        //前闭后开，[j+1,i)为所有大于v的元素的区间
        for (int i = j + 1; i <= right; i++) {
            //如果i小于了v，将i与第一个大于v的元素交换位置，然后j++，就保证了，[left + 1,j]的所有元素都小于v
            if (arr[i] < v){
                swap(arr,i,j+1);
                j++;
            }//如果不小于v，就继续遍历
        }
        //交换left和j（最后一个小于left的元素）
        swap(arr,left,j);
        return j;//返回
    }

    public void heapSort(int[] arr){
        //先最大堆化
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        //在进行堆排序
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    private void siftDown(int[] arr, int i, int length) {
        while (2 * i + 1 < length){
            int j = (2 * i) + 1;
            if (j + 1 < length && arr[j+1] > arr[j]){
                j = j+1;
            }
            if (arr[i] > arr[j]){
                break;
            }else {
                swap(arr,i,j);
                i = j;
            }
        }
    }

    private void swap(int[] arr, int min, int i) {
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}
